﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Union_Find
{
    public class UFV2 : IUF
    {
        private int[] id;
        private int count;
        public UFV2(int n)
        {
            count = n;
            id = new int[n];
            for (int i = 0; i < n; i++) id[i] = i;
        }

        public void Union(int p, int q)
        {
            int proot = Find(p);
            int qroot = Find(q);

            if (proot == qroot) return;

            id[proot] = qroot;

            count--;
        }

        public int Find(int p)
        {
            while (p != id[p]) p = id[p];
            return p;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Count => count;
    }
}
